package Algorithm.dynamic;

//背包问题
public class KnapsackProblem {
	public static void main(String[] args) {
		//物品重量
		int[] weight = {0, 1, 4, 3};
		//物品价值
		int[] value = {0, 1500, 3000, 2000};
		//背包容量
		int m = 5;
		//物品个数
		int n = value.length;


		//创建二维数组
		//v[i][j] 表示再前 i 个物品中能够装入容量为 j 的背包中的最大值
		int[][] v = new int[n][m + 1];

		//为记录放入商品的情况，定义一个二维数组
		int[][] path = new int[n][m + 1];

		//初始化第一行和第一列，可以不处理，默认全0
		for (int i = 0; i < v.length; i++) {
			v[i][0] = 0;
		}
		for (int i = 0; i < v[0].length; i++) {
			v[0][i] = 0;
		}

		//==动态规划======================
		for (int i = 1; i < v.length; i++) {//不处理第一行
			for (int j = 1; j < v[i].length; j++) {//不处理第一列
				if (weight[i] > j) {
					//若该物品的重量 大于 背包容量，就把上一个的结果赋给当前单元格
					v[i][j] = v[i - 1][j];
				} else {
					//若该物品的体积 小于等于 背包容量
					//就在（上一个结果）和（当前物品价值+剩余容量所能装的最大价值）中选取最大的
					//v[i][j] = Math.max(v[i-1][j], value[i]+v[i-1][j-weight[i]]);

					//为了记录商品放入的情况，不能直接使用上面的公式，需要使用 if-else
					if (v[i - 1][j] < value[i] + v[i - 1][j - weight[i]]) {
						v[i][j] = value[i] + v[i - 1][j - weight[i]];
						//记录当前路径
						//只有当有新的最大值时，才修改 path
						path[i][j] = 1;
					} else {
						//直接赋值上一个结果，没有产生新的最大值，不修改 path
						v[i][j] = v[i - 1][j];
					}
				}
			}
		}

		//输出表格==============================
		System.out.println("表格");
		for (int i = 0; i < v.length; i++) {
			for (int j = 0; j < v[i].length; j++) {
				System.out.print(v[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("路径表格");
		for (int i = 0; i < path.length; i++) {
			for (int j = 0; j < path[i].length; j++) {
				System.out.print(path[i][j] + " ");
			}
			System.out.println();
		}

		//输出结果==============================
		int i = path.length - 1;//行小标的最大值
		int j = path[0].length - 1;//列下标的最大值

		while (i > 0 && j > 0) {//从path 最后开始
			if (path[i][j] > 0) {
				System.out.printf("第%d个商品放入到背包\n", i);
				//减去当前物品的重量
				j -= weight[i];
			}
			i--;

		}


	}
}
